Lagrangian relaxation hybrid with evolutionary algorithm for short-term generation scheduling

Short-term generation scheduling is an important function in daily operational planning of power systems. It is defined as optimal scheduling of power generators over a scheduling period while respecting various generator constraints and system constraints. Objective of the problem includes costs associated with energy production, start-up cost and shut-down cost along with profits. The resulting problem is a large scale nonlinear mixed-integer optimization problem for which there is no exact solution technique available. The solution to the problem can be obtained only by complete enumeration, often at the cost of a prohibitively computation time requirement for realistic power systems. This paper presents a hybrid algorithm which combines Lagrangian Relaxation (LR) together with Evolutionary Algorithm (EA) to solve the problem in cooperative and competitive energy environments. Simulation studies were carried out on different systems containing various numbers of units. The outcomes from different algorithms are compared with that from the proposed hybrid algorithm and the advantages of the proposed algorithm are briefly discussed.     

A meta-heuristic optimization approach to the scheduling of bag-of-tasks applications on heterogeneous clouds with multi-level arrivals and critical jobs

As cloud computing evolves, it is becoming more and more apparent that the future of this industry lies in interconnected cloud systems where resources will be provided by multiple “Cloud” providers instead of just one. In this way, the hosts of services that are cloud-based will have access to even larger resource pools while at the same time increasing their scalability and availability by diversifying both their computing resources and the geographical locations where those resources operate from. Furthermore the increased competition between the cloud providers in conjunction with the commoditization of hardware has already led to large decreases in the cost of cloud computing and this trend is bound to continue in the future. Scientific focus in cloud computing is also headed this way with more studies on the efficient allocation of resources and effective distribution of computing tasks between those resources. This study evaluates the use of meta-heuristic optimization algorithms in the scheduling of bag-of-tasks applications in a heterogeneous cloud of clouds. The study of both local and globally arriving jobs has been considered along with the introduction of sporadically arriving critical jobs. Simulation results show that the use of these meta-heuristics can provide significant benefits in costs and performance.     

Project scheduling under partially renewable resources and resource consumption during setup operations

There has been an increasing pressure on manufacturing industries to reduce energy consumption. In this study, we propose a new variant of RCPSP called RCPSP/πRC, which can deal with realistic energy constraints such as power restriction during peak hours, contract demand, and energy consumption during setup operations. First, we present an integer programming (IP) model and a constraint programming (CP) model of the RCPSP/πRC. Next, we present a heuristic mode restriction method called a mask calculation algorithm to achieve efficient searching by restricting selectable modes. Finally, through computational experiments, we evaluate the proposed methods and show their effectiveness.     

Optimal scheduling of single stage batch plants with direct heat integration

This paper addresses the multi-objective optimization problem arising in the operation of heat integrated batch plants, where makespan and utility consumption are the two conflicting objectives. A new continuous-time MILP formulation with general precedence variables is proposed to simultaneously handle decisions related to timing, product sequencing, heat exchanger matches (selected from a two-stage superstructure) and their heat loads. It features a complex set of timing constraints to synchronize heating and cooling tasks, derived from Generalized Disjunctive Programming. Through the solution of an industrial case study from a vegetable oil refinery, we show that major savings in utilities can be achieved while generating the set of Pareto optimal solutions through the ɛ-constraint method.     

An optimization algorithm for the workforce management in a retail chain

This work proposes a scheduling problem for the workforce management in a chain of supermarkets operating in Italy. We focus on determining the ideal mix of full-time and part-time workers which are needed every week to guarantee a satisfactory service level during the check-out operations. The generation of working shifts, to be assigned to retail workers, is subject to several constraints imposed by both labour laws and enterprise bargaining agreements.We present a mathematical formulation of the problem followed by an exact solution approach which relies on the definition of feasible daily working shifts. The number of feasible daily shifts, that are combined to determine feasible weekly shifts, could drastically increase, depending on the selected planning interval. In addition, there may exist additional constraints, that are difficult to incorporate into the mathematical model. For these reasons, a hybrid heuristic, which does not require the generation of all feasible weekly shifts, is proposed in this paper.Using appropriate statistical techniques, a sensitivity analysis is performed to test the design of the hybrid heuristic. Computational tests are carried out by solving several real instances provided by the retail firm. The results obtained by the heuristic are compared both with an exact approach and with the solutions adopted by the retail company, which have been determined by using a naïf approach. Our hybrid heuristic exhibits excellent performance finding optimal or near optimal solutions in a very limited CPU time.     

Demand response for home energy management system

The optimization of energy consumption, with consequent cost reduction, is one of the main challenges for the present and future smart grid. Demand response (DR) program is expected to be vital in home energy management system (HEMS) which aims to schedule the operation of appliances to save energy costs by considering customer convenience as well as characteristics of electric appliances. The DR program is a challenging optimization problem especially when the formulations are non-convex or NP-hard problems. In order to solve this challenging optimization problem efficiently, an effective heuristic approach is proposed to achieve a near optimal solution with low computational costs. Different from previously proposed methods in literatures which are not suitable to be run in embedded devices such as a smart meter. The proposed algorithm can be implemented in an embedded device which has severe limitations on memory size and computational power, and can get an optimal value in real-time. Numerical studies were carried out with the data simulating practical scenarios are provided to demonstrate the effectiveness of the proposed method.     

Systematic tool to plan and evaluate demand side strategies during sustained energy crises in hydrothermal power systems

HARE, a systematic tool to evaluate demand side measures to face sustained energy supply risk in hydrothermal power systems is presented in this paper. The main focus of the paper is to help centralized planners to systematically discuss, select, and plan the measures that better respond to the variety of critical situations that can arise due to expected energy shortage, integrate them into the usual medium-term scheduling tool and consequently keep the associated overall costs as low as possible. A medium-term definition of the system state is proposed as a decision-making aid, as well as a set of general energy saving measures that can be applied with their corresponding attributes (time delays, costs of implementation, and energy saving impact). The tool is demonstrated and applied to a simplified version of Chilean’s medium-term hydrothermal scheduling model and to a specific risk scenario experienced during 2011. The results show that it is possible to define various sets of demand side measures that avoid the impacts on the system and subsequently to select among them those with least expected implementation costs. This tool seems mainly useful for hydro-electric systems, which are more vulnerable to sustained energy supply risk. Every power system will have to go through a detailed review and planning process to implement this type of tool.     

Automatic design for shop scheduling strategies based on hyper-heuristics: A systematic review

Against the background of smart manufacturing and Industry 4.0, how to achieve real-time scheduling has become a problem to be solved. In this regard, automatic design for shop scheduling based on hyper-heuristics has been widely studied, and a number of reviews and scheduling algorithms have been presented. Few studies, however, have specifically discussed the technical points involved in algorithm development. This study, therefore, constructs a general framework for automatic design for shop scheduling strategies based on hyper-heuristics, and various state-of-the-art technical points in the development process are summarized. First, we summarize the existing types of shop scheduling strategies and classify them using a new classification method. Second, we summarize an automatic design algorithm for shop scheduling. Then, we investigate surrogate-assisted methods that are popular in the current algorithm field. Finally, current problems and challenges are discussed, and potential directions for future research are proposed.